//
//  ProblemOffer35.swift
//  LeetCode
//
//  Created by 武侠 on 2022/3/11.
//  Copyright © 2022 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 剑指 Offer 35. 复杂链表的复制
 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

 示例 1：
     输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
     输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 示例 2：
     输入：head = [[1,1],[2,1]]
     输出：[[1,1],[2,1]]
 示例 3：
     输入：head = [[3,null],[3,0],[3,null]]
     输出：[[3,null],[3,0],[3,null]]
 示例 4：
     输入：head = []
     输出：[]
 解释：给定的链表为空（空指针），因此返回 null。
  
 提示：
    -10000 <= Node.val <= 10000
    Node.random 为空（null）或指向链表中的节点。
    节点数目不超过 1000 。
 */
class ProblemOffer35: NSObject {
    func copyRandomList(_ head : RandomNode?) -> RandomNode? {
        if head == nil {
            return nil
        }
        
        var fhead:RandomNode? = RandomNode(_val: head!.val)
        let result = fhead
        var list: [RandomNode] = [fhead!]
        
        var nextNode = head?.next
        while nextNode != nil {
            // 创建一个新的Node
            fhead?.next = RandomNode(_val: nextNode!.val)
            nextNode = nextNode?.next
            fhead = fhead?.next
            list.append(fhead!)
        }
        
        nextNode = head
        fhead = result
        while fhead != nil {
//            fhead?.random = nextNode?.random == nil ? nil : list[nextNode!.random]
            
            fhead = fhead?.next
            nextNode = nextNode?.next
        }
        
        return result
    }
}
